/*
 * @time : 2022/5
 * @author : liyajun
 * @homepage : moreac.top
 */
#include <bits/stdc++.h>

const int N = 1e6+10;

using namespace std;

int arr[N],b[N],tem[N];
int n;
//递归
void merge_rec(int l,int r)
{
	if(l >= r) return;
	
	int mid = l + r >> 1;
	
	merge_rec(l,mid),merge_rec(mid+1,r);
	
	int i = l,j = mid + 1,k = 0;
	
	while(i <= mid and j <= r)
	{
		if(arr[i] <= arr[j]) b[k++] = arr[i++];
		else b[k++] = arr[j++];
	}
	while(i <= mid) b[k++] = arr[i++];
	while(j <= r) b[k++] = arr[j++];
	for(int i = 0,j = l;j <= r;i++,j++)arr[j] = b[i];
}
// 迭代
void merge()
{
	 int i, next, left_min, left_max, right_min, right_max;
	 for(int i = 1;i < n;i*=2)
	 {
	 	for(left_min = 0;left_min < n-i;left_min = right_max)
	 	{
	 		right_min = left_max = left_min + i;
            right_max = left_max + i;
            if(right_max > n) right_max = n;
            next = 0;
            while(left_min < left_max and right_min < right_max)
            {
            	if(arr[left_min] < arr[right_min]) tem[next++] = arr[left_min++];
            	else tem[next++] = arr[right_min++];
            }
            while(left_min < left_max)arr[--right_min] = arr[--left_max];
            while(next > 0)arr[--right_min] = tem[--next];
	 	}
	 }
}
void slove()
{
	cin >> n;
	
	for(int i = 0;i < n;i++)cin >> arr[i];
	//迭代
	merge();
	//递归
	merge_rec(0,n-1);
}
int main() {
	int T = 1;
	//cin >> T;
	while(T--)slove();



	return 0;
}

